package leetcode.str;

public class Test459 {

    public static void main(String[] args) {
        boolean abac = repeatedSubstringPattern("aabaabaab");
        //ababcababc
        //001 123 42
        System.out.println(abac);
    }

    public static boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        if (length == 1){
            return false;
        }
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = j;
        int strLength = 0;
        for (int i = 1; i < next.length; i++) {
            while (j>0 && chars[i] != chars[j]){
                j = next[j-1];
            }
            if (chars[i] == chars[j]){
                j++;
            }
            if (i == j*2){
                strLength = j;
            }
            next[i] = j;
        }
        int index = strLength+1;
        int i = 0;
        while (index<length){
            if(chars[i] == chars[index]){
                if(i == strLength){
                    i = 0;
                }
                else{
                    i++;
                }

                index++;
            }
            else{
                return false;
            }
        }
        if (i != 0){
            return false;
        }
        return true;
    }
}
